package cs271.examples.recursion;

public class Fibonacci {
	
	/**
	 * Calculate the nth fibonacci number in a fantasically slow way.
	 * This is an example of how NOT to use recursion.
	 * @param n
	 * @return nth fibonacci number
	 */
	public static int fib(int n) {
		if(n<=2)
			return 1;
		else
			return fib(n-1) + fib(n-2);
	}
	
	
	public static int fib_iter(int n) {
		int prev = 0;
		int current = 1;
		for(int i = 1; i<n; i++) {
			int temp = current;
			current = current+prev;
			prev = temp;
		}
		return current;
	}
	
	public static void main(String[] args) {
		long start, end;
		start = System.currentTimeMillis();
		fib(45);
		end = System.currentTimeMillis();
		System.out.println((end-start));
	}
}
